/*
 * @lc app=leetcode.cn id=235 lang=cpp
 *
 * [235] 二叉搜索树的最近公共祖先
 */

// @lc code=start

#include <bits/stdc++.h>
using namespace std;

// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };


class Solution {
    void findPath(TreeNode* r, vector<TreeNode*>& v, TreeNode* target)
    {
        v.push_back(r);
        if(r == target)
        {
            return;
        }
        if(target->val < r->val)
        {
            findPath(r->left, v, target);
        }
        else
        {
            findPath(r->right, v, target);
        }
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(nullptr == root)
            return root;
        vector<TreeNode*> v1, v2;
        findPath(root, v1, p);
        findPath(root, v2, q);

        const int N = v1.size() < v2.size() ? v1.size() : v2.size();
        for(int i = 0; i < N; i++)
        {
            if(v1[i] != v2[i]) return v1[i-1];
        }
        if(v1.size() < v2.size()) return (*(v1.end()-1));
        else return (*(v2.end()-1));

        // return root;
    }
};
// @lc code=end

